package com.gitee.ywj1352.算法.week01;

import java.util.Arrays;

public class 快排 {

    public static int[] MySort(int[] arr) {
        quickSort2(arr, 0, arr.length - 1);
        return arr;
    }


    private static void quickSort(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }
        int l = left, r = right, base = arr[left];
        while (l < r) {
            while (base <= arr[r] && l < r) {
                r--;
            }
            while (base >= arr[l] && l < r) {
                l++;
            }
            //交换
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
        }
        //基准位 归为
        arr[left] = arr[l];
        arr[l] = base;

        //递归执行
        quickSort(arr, left, l - 1);
        quickSort(arr, l + 1, right);
    }


    public static int partition(int[] a, int l, int r) {
        int base = a[l];
        while (l < r) {
            while (a[r] >= base && r > l) r--;
            a[l] = a[r];
            while (a[l] <= base && r > l) l++;
            a[r] = a[l];
        }
        a[l] = base;
        return l;
    }

    public static int p(int[] arr, int l, int r) {
        int b = arr[l];
        while (l < r) {
            while (arr[r] >= b && r > l) r--;
            arr[l] = arr[r];
            while (arr[l] <= b && r > l) l--;
            arr[r] = arr[l];
        }
        arr[l] = b;
        return l;
    }

    private static void quickSort2(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }
        int p = partition(arr, left, right);
        quickSort2(arr, left, p - 1);
        quickSort2(arr, p + 1, right);
    }

    public static void merge2(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1]; // 中间数组
        int i = left, j = mid + 1, k = 0;
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        for (int p = 0; p < temp.length; p++) {
            arr[left + p] = temp[p];
        }
    }


    public static boolean increasingTriplet(int[] nums) {
        int m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE;
        for (int n : nums) {
            if (n <= m1) {
                m1 = n;
            } else if (m2 >= n) {
                m2 = n;
            } else {
                return true;
            }
        }
        return false;
    }


    public static boolean find132pattern(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int m1 = nums[i], m2 = 0;
            for (int j = i + 1; j < nums.length; j++) {
                if (m1 < nums[j] && m2 < m1) {
                    m2 = nums[j];
                } else {
                    if (nums[j] > m1 && nums[j] < m2) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];

        int l = left, m = mid, i = 0;

        while (l <= mid && right >= m) {
            //temp[i++]
            temp[i++] = arr[l] > arr[m] ? arr[m++] : arr[l++];
        }
        while (l <= mid) {
            temp[i++] = arr[l++];
        }
        while (right >= m) {
            temp[i++] = arr[m++];
        }
        System.arraycopy(temp, 0, arr, left , temp.length);


    }

    public static void main(String[] args) {
        int amount = 10;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        System.out.println(Arrays.toString(dp));

    }





    public void ms(int[] a , int l , int r){
        if(l >= r) return ;
        int m = (l+r) >> 1;
        ms(a, l , m);
        ms(a,m+1,r);
        merge3(a,l,m,r);
    }
    public void merge3(int[] a, int left, int mid ,int r){
        int[] temp = new int[r -left +1];
        int l = left,m = mid+1,i = 0 ;
        while(l <= mid && m <= r){
            temp[i++] = a[l] >= a[m]?a[m++]:a[l++];
        }
        while(l <= mid) temp[i++] = a[l++];
        while(m <= r) temp[i++] = a[m++];
        System.arraycopy(temp, 0, a, left , temp.length);
    }
}
